package leetcode4;
import java.util.*;
public class Day15 {
    //474.一和零
    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        int[][] dp = new int[m+1][n+1];
        //从前i个字符串中挑选，字符0的个数不超过j，字符1的个数不超过k的最大子集长度
        for(int i=1;i<len+1;i++) {
            //记录当前字符串子集的0和1个数
            int a = 0, b = 0;
            for(int z=0;z<strs[i-1].length();z++) {
                if(strs[i-1].charAt(z) == '0') a++;
                else b++;
            }
            for(int j=m;j>=a;j--) {
                for(int k=n;k>=b;k--) {
                    dp[j][k] = Math.max(dp[j][k],dp[j-a][k-b]+1);
                }
            }
        }
        return dp[m][n];
    }

    //最长回文串
    public int longestPalindrome(String s) {
        Map<Character,Integer> map = new HashMap<>();
        //1.统一每个字符出现的次数
        for(char ch : s.toCharArray()) {
            map.put(ch,map.getOrDefault(ch,0)+1);
        }
        //2.记录
        boolean bool = false;
        int ret = 0;
        for (Integer value : map.values()) {
            if(value %2 == 0) {
                //3.偶数
                ret += value;
            }else {
                //4.奇数
                bool = true;
                ret += value - 1;
            }
        }
        if(bool) ret++;
        return ret;
    }

    public static void main(String[] args) {

    }
}
